/* 
  实现一个选择排序
  循环不变量：数组的[0, i)时有序的，[i, n)是无序的
  处理方式：
    每次都取一个元素出来和后面的比较，找出最小的哪个元素放在前面的位置上
*/
function swap(arr, i, j) {
  const temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let minIndex = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    swap(arr, i, minIndex);
  }
}

/* 
  实现一个插入排序
  循环不变量：数组的[0, i)时有序的，[i, n)是无序的
  处理方式：
    每次都取一个元素出来和后面的比较，然后把这个元素放在前面已经排好序的正确位置
*/
function insertSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i; j - 1 >= 0; j--) {
      if (arr[j - 1] > arr[j]) {
        swap(arr, j, j - 1);
      } else {
        // 说明已经在正确的位置了
        break;
      }
    }
  }
}

// 不使用交换的方式实现，而是使用赋值的方式实现
function insertSort2(arr) {
  for (let i = 0; i < arr.length; i++) {
    let t = arr[i];
    let insertIndex;
    for (insertIndex = i; insertIndex - 1 >= 0; insertIndex--) {
      if (arr[insertIndex - 1] > t) {
        arr[insertIndex] = arr[insertIndex - 1];
      } else {
        break;
      }
    }
    arr[insertIndex] = t;
  }
}

function testSort() {
  const arr = [78, 2, 4, 6, 1, 3, 9, 8, 23, 13];
  console.log('排序前：', arr.toString());
  // selectionSort(arr);
  insertSort2(arr);
  console.log('排序后：', arr.toString());
}
// testSort();

(function () {
  const selectionSort = (arr) => {
    for (let i = 0; i < arr.length; i++) {
      let minIndex = i;
      for (let j = i + 1; j < arr.length; j++) {
        if (arr[j] < arr[minIndex]) {
          minIndex = j;
        }
      }
      swap(arr, i, minIndex);
    }
  };
  const insertSort = (arr) => {
    for (let i = 0; i < arr.length; i++) {
      for (let j = i; j - 1 >= 0; j--) {
        if (arr[j - 1] > arr[j]) {
          swap(arr, j, j - 1);
        } else {
          break;
        }
      }
    }
  };
  const arr = [78, 2, 4, 6, 1, 3, 9, 8, 23, 13];
  console.log('排序前：', arr.toString());
  selectionSort(arr);
  // insertSort2(arr);
  console.log('排序后：', arr.toString());
})();


